/**
 * @program: 力扣刷题
 * @description：最长回文子串问题：正读、反读都一样.
 * @author: LiChong
 * @create: 2021-05-25 15:53
 **/
public class Code05 {
    public static void main(String[] args) {
        String s = longestPalindrome2("d");
        System.out.println(s);
    }
    /**
     * 解法一，暴力遍历,太慢，过不了力扣的测试用例
     * @param s
     * @return
     */
    public static String longestPalindrome(String s){
        if (s==null||s.length()==0){
            return null;
        }
        if(s.length()==1){
            return s;
        }
        int maxLength = 0;
        int start =0,end =0;
        for (int i = 0; i <s.length() ; i++) {
            for (int j = i+1; j <=s.length() ; j++) {
                String str = s.substring(i,j);
                if (ifPalindrome(str)){
                    if (str.length()>maxLength){
                        maxLength = str.length();
                        start = i;
                        end = j ;
                    }
                }
            }
        }
        return s.substring(start,end) ;
    }
    public static boolean ifPalindrome(String s){
        for (int i = 0; i <s.length()/2 ; i++) {
            if (s.charAt(i)==s.charAt(s.length()-1-i)){

            }else {
                return false;
            }
        }
        return true;

    }
    /**
     * 解法二：中心拓展法
     */
    public static String longestPalindrome2(String s){
        if (s==null||s.length()==0){
            return null;
        }
        if(s.length()==1){
            return s;
        }
        int len = s.length();
        int left=0,right=0,maxLength=0,maxStart=0,maxEnd=0;
        for (int i = 0; i <len ; i++) {
            left=i-1;
            right=i+1;
            while(left>=0&&s.charAt(left)==s.charAt(i)){
                left--;
            }
            if(left<0){
                left = 0;
            }else {
                left = left+1;
            }
            while(right<=len-1&&s.charAt(right)==s.charAt(i)){
                right++;
            }
            if(right>len-1){
                right = len-1;
            }else {
                right = right-1;
            }
            int length = right-left +1;
            if (length>maxLength){
                maxLength = length;
                maxStart = left;
                maxEnd = right;
            }
            if (left==0||right ==len-1){
                continue;
            }
            while(left>=0&&right<=s.length()-1){
                if (s.charAt(left)==s.charAt(right)){
                    int curLength = right-left+1;
                    if (curLength>maxLength){
                        maxLength = curLength;
                        maxStart = left;
                        maxEnd = right;
                    }
                    left--;
                    right++;
                }else {
                    break;
                }
            }
        }
        return s.substring(maxStart,maxEnd+1);
    }


}
